package cn.zuo.utils;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
 * @Author 白白旧维
 * @Date 2021/7/7 11:13
 */
public class StrongPrimes {

    private static List<BigInteger> strongPrimes = new ArrayList<>();



    public static List<BigInteger> get_strongPrimes(int n){

        for(int i=0;i<n;i++){
            strongPrimes.add(get_strongPrime_one(new Random().nextLong(),"100000000000000000000","500000000000000000000"));
            System.out.println("添加第"+(i+1)+"个成功");
        }

        return strongPrimes;

    }


    public static BigInteger get_strongPrime_one(long random,String up,String down){

        //随机大素数p//不过后边最好是大于10^18
        BigInteger p = new BigInteger("0");
        BigInteger doge = new BigInteger(up);//10^20
        int offset = Math.abs(new Random(random).nextInt()%10);//随机偏移1000位
        BigInteger sushu = new BigInteger("10000001");
        while(doge.compareTo(new BigInteger(down))==-1){//5*10^20
            if(offset==0){
                p=sushu;
                break;
            }
            if(isPrime(doge)){//是素数就再找下一个素数
                sushu=doge;
                offset--;
            }
            doge = doge.add(new BigInteger("3"));
        }

//        System.out.println("找到素数p");

        //随机整数m（小于970亿亿）
        BigInteger m = new BigInteger(Math.abs(new Random(random).nextLong())+"");
//        System.out.println("随机整数m");

        //素数q
        BigInteger q = null;
        BigInteger i = m;
        while(true){
            q = new BigInteger("2").multiply(i).multiply(p).add(new BigInteger("1"));
            if(isPrime(q)){
                break;
            }
            i = i.add(new BigInteger("1"));
        }

//        System.out.println("找到素数q");



        //随机整数n（小于970亿亿）
        BigInteger n = new BigInteger(Math.abs(new Random(random).nextLong())+"");
//        System.out.println("随机整数n");

        //计算强素数s
        BigInteger s = null;

        BigInteger r = null;
        BigInteger prer = new BigInteger("0");
        BigInteger j = n;
        while(true){
            while(true){
                r = new BigInteger("2").multiply(j).multiply(p).add(new BigInteger("1"));
                if(isPrime(r)&&prer.compareTo(r)!=0){
                    prer = r;
                    break;
                }
                j = j.add(new BigInteger("1"));
            }
            s = new BigInteger("2").multiply(r).subtract(new BigInteger("1"));
            if(isPrime(s)){
                break;
            }
            System.out.println(s+"不是素数，丢弃!!");
        }

        return s;
    }




    private static boolean isPrime(BigInteger p) {//判断是否为素数，返回true为素数，否则不为素数
        //BigInteger类是进行大数运算使用的类

        if((p.mod(new BigInteger("6")).compareTo(new BigInteger("1"))!=0)&&(p.mod(new BigInteger("6")).compareTo(new BigInteger("5"))!=0)){
            return false;
        }

        BigInteger res = my_pow(new BigInteger("2"), p.subtract(new BigInteger("1")), p);

        if (res.compareTo(new BigInteger("1")) != 0) {
            return false;
        } else {
            return true;
        }
    }

    private static BigInteger my_pow(BigInteger x,BigInteger n,BigInteger m){//蒙哥马利算法
        BigInteger r = new BigInteger("1");//最终求余结果
        while(n.compareTo(new BigInteger("0"))==1){
            if(n.mod(new BigInteger("2")).compareTo(new BigInteger("1"))==0) {//只要幂次最低位为1就可以更新结果
                r = r.multiply(x).mod(m);
            }
            n = n.divide(new BigInteger("2"));
            x = x.multiply(x).mod(m);
        }
        return r;
    }



}
